import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/18 10:39
 * @description 字典树 + 记忆化搜索
 */
public class Solution {
    Trie trie = new Trie();
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> ans = new ArrayList<>();
        int n = s.length();
        for (String a : wordDict) {
            insert(a);
        }
        boolean[] visited = new boolean[n];
        dfs(s, ans, visited, 0);
        return ans;
    }

    public void dfs(String s, List<String> ans, boolean[] visited, int start) {
        if (start == s.length()) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                sb.append(s.charAt(i));
                if (visited[i] && i!= s.length() - 1) {
                    sb.append(" ");
                }
            }
            ans.add(sb.toString());
            return;
        }
        Trie node = trie;
        for (int i = start; i < s.length(); i++) {
            char ch = s.charAt(i);
            int index = ch - 'a';
            node = node.children[index];
            if (node == null) {
                return;
            }
            if (node.isEnd) {
                visited[i] = true;
                dfs(s, ans, visited, i + 1);
                visited[i] = false;
            }
        }
    }

    public void insert(String word) {
        Trie node = trie;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }


}

class Trie {
    Trie[] children;
    boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
}